package com.example.rwq_test.niuke.tree;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * 序列化树
 *
 * @author renweiqiang
 * @version 1.0.0
 * @createTime 2023/11/17
 */
public class SerializeTree {
    private static final String SPLIT = "#";
    private static final String EMPTY = " ";

    public static String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        String serialize = "";

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (poll == null) {
                serialize = serialize + EMPTY + SPLIT ;
                continue;
            }
            serialize = serialize + poll.val + SPLIT;
            queue.offer(poll.left);
            queue.offer(poll.right);
        }
        return serialize;
    }

    public static TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        String[] split = data.split(SPLIT);
        TreeNode root = new TreeNode(Integer.valueOf(split[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        for (int i = 1; i < split.length - 1; i++) {
            TreeNode node = queue.poll();
            if (node == null) {
                continue;
            }
            String s = split[i];
            if (!Objects.equals(s, EMPTY)) {
                TreeNode treeNode = new TreeNode(Integer.valueOf(s));
                node.left = treeNode;
                queue.offer(treeNode);
            }
            s = split[++i];
            if (!Objects.equals(s, EMPTY)) {
                TreeNode treeNode = new TreeNode(Integer.valueOf(s));
                node.right = treeNode;
                queue.offer(treeNode);
            }
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode0 = new TreeNode(0);
        TreeNode treeNode8 = new TreeNode(8);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode9 = new TreeNode(9);

        treeNode3.left = treeNode5;
        treeNode3.right = treeNode1;
        treeNode5.left = treeNode6;
        treeNode5.right = treeNode2;
        treeNode1.left = treeNode0;
        treeNode1.right = treeNode8;
        treeNode2.left = treeNode7;
        treeNode2.right = treeNode4;
        treeNode8.right = treeNode9;

        System.out.println(serialize(treeNode3));;
    }
}
